package com.LeetCode.DFS;

import com.LeetCode.Tree.TrieTree;
import org.junit.Test;
import sun.text.normalizer.Trie;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * 单词查找
 */
public class FindWords {

    private class TrieTree{

        private class TrieNode{

            private TrieNode[] children;

            boolean isEnd;

            public TrieNode(){
                this.children = new TrieNode[26];
                this.isEnd = false;
            }
        }

        private TrieNode root;

        public TrieTree(){
            root = new TrieNode();
        }

        public void insert(String word){
            TrieNode node = this.root;
            for(int i = 0; i<word.length(); i++){
                if(node.children[word.charAt(i) - 'a'] == null){
                    node.children[word.charAt(i) - 'a'] = new TrieNode();
                }
                node = node.children[word.charAt(i) - 'a'];
            }
            node.isEnd = true;
        }

        public boolean search(String word){
            TrieNode node = this.root;
            for(int i = 0; i<word.length(); i++){
                if(node.children[word.charAt(i) - 'a'] == null){
                    return false;
                }
                node = node.children[word.charAt(i) - 'a'];
            }
            return node.isEnd;
        }

        public boolean startWith(String prefix){
            TrieNode node = this.root;
            for(int i = 0; i<prefix.length(); i++){
                if(node.children[prefix.charAt(i) - 'a'] == null){
                    return false;
                }
                node = node.children[prefix.charAt(i) - 'a'];
            }
            return true;
        }

    }

    TrieTree trieTree;


    HashSet<String> set = new HashSet<>();

    HashSet<String> res = new HashSet<>();

    char[][] board;

    int maxLen;

    public List<String> findWords(char[][] board, String[] words) {
        for(String str : words){
            set.add(str);
            maxLen = Math.max(maxLen, str.length());
        }

       this.trieTree = new TrieTree();

        for(String str : words){
            this.trieTree.insert(str);
        }

        this.board = board;

        for(int i = 0; i<board.length; i++){
            for(int j = 0; j<board[0].length; j++){
                if(this.trieTree.startWith("" + board[i][j]))
                    dfs(i, j, "");
            }
        }

        return new ArrayList<>(res);

    }

    public void dfs(int i, int j, String cur){
        if (set.contains(cur)) {
            res.add(cur);
        }

        if(i < 0 || i >= board.length || j < 0 || j >= board[0].length
                || board[i][j] == '/' || cur.length() > maxLen || !this.trieTree.startWith(cur))
            return;

        cur += board[i][j];

        if(!this.trieTree.startWith(cur)){
            return;
        }

        char tmp = board[i][j];

        board[i][j] = '/';

        dfs(i+1, j, cur);
        dfs(i-1, j, cur);
        dfs(i, j+1, cur);
        dfs(i, j-1, cur);

        board[i][j] = tmp;
    }

    @Test
    public void test(){
        char[][] board = {
                {'o','a','a','n'},
                {'e','t','a','e'},
                {'i','h','k','r'},
                {'i','f','l','v'}
        };
        String[] words1 = {"oath","pea","eat","rain"};

        char[][] board2 = {
                {'a','b'},
                {'a','a'}
        };
        String[] words2 = {"aba","baa","bab","aaab","aaa","aaaa","aaba"};

        System.out.println(findWords(board2,words2));
    }
}
